from .search import width_first


class Graph:
    def __init__(self):
        self._nodes = {}

    def regist(self, name, value):
        assert name not in self._nodes, "'%s' is duplicated" % name
        node = _Node(name, value)
        self._nodes[name] = node
        return node

    def get_node_value(self, name):
        return self._nodes[name].value

    def get_node_values(self):
        return [node.value for node in self._nodes.values()]

    def get_node_names(self):
        return self._nodes.keys()

    def has_node(self, name):
        return name in self._nodes

    def get_nodes(self):
        return [(name, node.value) for name, node in self._nodes.items()]

    def navigate_nodes(self, func):
        for name, node in self._nodes.items():
            func(name, node.value)

    def get_edges(self):
        result = []
        for name, node in self._nodes.items():
            edge = node.next_src
            while edge is not node:
                result.insert(0, (node.name, edge.dst.name, edge.value))
                edge = edge.next_src
        return result

    def navigate_edges(self, func):
        for name, node in self._nodes.items():
            edge = node.next_src
            while edge is not node:
                func(node.name, edge.dst.name, edge.value)
                edge = edge.next_src

    def connect(self, name_src, name_dst, value=None):
        """
        Connect the two buffers.
        :param name_src: the source buffer name, None means the head.
        :param name_dst: the destination buffer name, None means the tail
        :return:
        """
        assert not (name_src is None or name_dst is None), 'name_src and name_dst are both not permitted to be None.'
        src_node = self.head if name_src is None else self._nodes[name_src]
        dst_node = self.tail if name_dst is None else self._nodes[name_dst]

        edge = _Edge(src_node, dst_node, value)

        edge.next_dst = src_node.next_dst
        src_node.next_dst = edge
        edge.prev_dst = src_node
        edge.next_dst.prev_dst = edge

        edge.next_src = dst_node.next_src
        dst_node.next_src = edge
        edge.prev_src = dst_node
        edge.next_src.prev_src = edge

    def disconnect(self, name_src, name_dst):
        edge = self._get_edge(name_src, name_dst)
        edge.next_dst.prev_dst = edge.prev_dst
        edge.prev_dst.next_dst = edge.next_dst
        edge.next_src.prev_src = edge.prev_src
        edge.prev_src.next_src = edge.next_src
        return edge.value

    def _get_edge(self, name_src, name_dst):
        src_head = self._nodes[name_src]
        edge = src_head.next_dst
        dst = self._nodes[name_dst]
        while edge != src_head and edge.dst != dst:
            edge = edge.next_dst
        assert edge != src_head, '%s is not connected with %s' % (name_src, name_dst)
        return edge

    def has_edge(self, src_name, dst_name):
        src_head = self._nodes[src_name]
        edge = src_head.next_dst
        dst = self._nodes[dst_name]
        while edge != src_head and edge.dst != dst:
            edge = edge.next_dst
        return edge != src_head

    def get_edge_value(self, name_src, name_dst):
        return self._get_edge(name_src, name_dst).value

    def get_children(self, name):
        node = self._nodes[name]
        result = []
        edge = node.next_dst
        while edge is not node:
            result.insert(0, edge.dst.name)
            edge = edge.next_dst
        return result

    def get_parents(self, name):
        node = self._nodes[name]
        result = []
        edge = node.next_src
        while edge is not node:
            result.insert(0, edge.src.name)
            edge = edge.next_src
        return result

    def move_parent_bottom(self, parent_name, name):
        """
        移动parent_name, 使之成为name的最后一个父节点。如果前者并不是后者的父节点之一，则扔出AssertError异常
        """
        value = self.disconnect(parent_name, name)
        self.connect(parent_name, name, value)

    def get_ancestors(self, name):
        result = []
        open = [self._nodes[name]]
        index = 0
        while index < len(open):
            node = open[index]
            result.append(node.name)
            edge = node.next_src
            while edge != node:
                if edge.src not in open:
                    open.append(edge.src)
                edge = edge.next_src
        return result

    def get_descendants(self, name):
        result = []
        open = [self._nodes[name]]
        index = 0
        while index < len(open):
            node = open[index]
            result.append(node.name)
            edge = node.next_dst
            while edge != node:
                if edge.dst not in open:
                    open.append(edge.dst)
                edge = edge.next_dst
        return result

    def __repr__(self):
        src = []
        for name in self._nodes:
            node = self._nodes[name]
            src.append(str(node) + ':')
            p = node.next_dst
            while p != node:
                src.append('\t%s' % p)
                p = p.next_dst
        return '\n'.join(src)

    def get_sub_graph(self, names):
        """
        返回由names中的结点构成的子图。
        """
        g = Graph()
        for name in names:
            if not g.has_node(name):
                g.regist(name, self.get_node_value(name))
            for parent in self.get_parents(name):
                if parent in names:
                    if not g.has_node(parent):
                        g.regist(parent, self.get_node_value(parent))
                    g.connect(parent, name, self.get_edge_value(parent, name))
        return g

    def topology(self):
        """返回结点名字的列表，结点之间按照拓扑排序原则排序，排在最前面的结点的入度为0"""
        current = {id: self.get_in_degree(id) for id in self._nodes}
        result = []
        while len(current) > 0:
            heads = [id for id, degree in current.items() if degree == 0]
            if len(heads) == 0:
                break
            for id in heads:
                del current[id]
            result.extend(heads)
            for id in heads:
                for child_id in self.get_children(id):
                    current[child_id] -= 1
        return result

    def get_in_degree(self, name):
        node = self._nodes[name]
        result = 0
        edge = node.next_src
        while edge is not node:
            result += 1
            edge = edge.next_src
        return result

    def get_out_degree(self, name):
        node = self._nodes[name]
        result = 0
        edge = node.next_dst
        while edge is not node:
            result += 1
            edge = edge.next_dst
        return result

    def get_heads(self):
        """
        返回所有头的名字列表。头就是入度为0的结点
        """
        return [name for name, node in self._nodes.items() if node.next_src is node]

    def get_tails(self):
        """
        返回所有尾巴的名字列表。尾巴就是出度为0的结点
        """
        return [name for name, node in self._nodes.items() if node.next_dst is node]

    def unti_topology(self):
        """返回结点名字的列表，结点之间按照反拓扑排序原则排序，排在最前面的结点的出度为0"""
        current = {id: self.get_out_degree(id) for id in self._nodes}
        result = []
        while len(current) > 0:
            heads = [id for id, degree in current.items() if degree == 0]
            if len(heads) == 0:
                break
            for id in heads:
                del current[id]
            result.extend(heads)
            for id in heads:
                for parent_id in self.get_parents(id):
                    current[parent_id] -= 1
        return result

    def get_ends(self):
        """
        返回所有起点的名字列表。起点就是入度为0的结点
        """
        return [name for name, node in self._nodes.items() if node.next_src is node]


class _Node:
    def __init__(self, name, value):
        self.name = name
        self.value = value
        self.next_dst = self
        self.next_src = self
        self.prev_dst = self
        self.prev_src = self

    def __repr__(self):
        return '%s(%s)' % (self.name, self.value)


class _Edge:
    def __init__(self, src, dst, value):
        self.src = src
        self.dst = dst
        self.value = value
        self.next_dst = None
        self.next_src = None
        self.prev_dst = None
        self.prev_src = None

    def __repr__(self):
        return "%s --%s--> %s" % (self.src.name, '' if self.value is None else ('%s' % self.value), self.dst.name)


if __name__ == '__main__':
    m = Graph()
    m.regist('b1', 1)
    m.regist('b2', 2)
    m.regist('b3', 3)
    m.regist('b4', 4)
    m.regist('b5', 5)
    m.regist('b6', 6)

    m.connect('b1', 'b2', 12)
    m.connect('b1', 'b3', '13')
    m.connect('b2', 'b4', '24')
    m.connect('b3', 'b5', 35)
    m.connect('b4', 'b6', 46)
    m.connect('b5', 'b6', 56)

    for name in m.get_names():
        print(name, m.get_node_value(name))

    print(m)
    m.disconnect('b5', 'b6')
    print('-' * 50)
    print(m)

